#include "BTreeNode.h"
#include <stdlib.h>

using namespace std;

// LEAF: helper macros
#define ENTRY_SIZE (sizeof(RecordId)+sizeof(int))
#define TOTAL_ENTRIES (getKeyCount())
#define TOTAL_SPACE (PageFile::PAGE_SIZE-sizeof(PageId)-sizeof(int)-sizeof(PageId)-sizeof(int)) // subtract PageId size for the pointer at the end of the node and int for the number of keys. Then we also have space to hold rootPID and treeHeight.
#define TAKEN_SPACE (getKeyCount()*ENTRY_SIZE)
//#define OFFSET_KEY      TOTAL_SPACE + sizeof(PageId)+sizeof(int)


// NONLEAF
#define NL_ENTRY_SIZE (sizeof(PageId)+sizeof(int))
#define NL_TAKEN_SPACE (getKeyCount()*NL_ENTRY_SIZE + sizeof(PageId))
#define NL_TOTAL_SPACE (TOTAL_SPACE)
#define NL_TOTAL_ENTRIES (TOTAL_ENTRIES)
#define NL_OFFSET_PID (sizeof(PageId))

#define OFFSET_ROOTPID TOTAL_SPACE
#define OFFSET_TREEHEIGHT (OFFSET_ROOTPID + sizeof(PageId))
#define OFFSET_KEY      (OFFSET_TREEHEIGHT + sizeof(int))
#define OFFSET_NEXTPTR  (OFFSET_KEY + sizeof(int))

// Helper function

/*
    Increments the key which is held at the end of the node's buffer.
    Function works for both leaf and nonleaf nodes given that
    TOTAL_SPACE == NL_TOTAL_SPACE
 */
void incrementKey(char* buffer) {
    // Get the key from the buffer, increment it, write back to the buffer
    int key = 0;
    memcpy(&key,buffer+OFFSET_KEY, sizeof(int));
    key++;
    memcpy(buffer + OFFSET_KEY, &key, sizeof(int));
}

void decrementKey(char* buffer) {
    // Get the key from the buffer, increment it, write back to the buffer
    int key = 0;
    memcpy(&key,buffer+OFFSET_KEY, sizeof(int));
    key--;
    memcpy(buffer + OFFSET_KEY, &key, sizeof(int));
}

void setKey(char* buffer, int key) {
    memcpy(buffer + OFFSET_KEY, &key, sizeof(int));
}


// LEAF ACCESSOR FUNCTIONS
int BTLeafNode::getHeight() {
    int h = 0;
    memcpy(&h, buffer + OFFSET_TREEHEIGHT, sizeof(int));
    return h;
}

void BTLeafNode::setHeight(int h) {
    memcpy(buffer + OFFSET_TREEHEIGHT, &h, sizeof(int));
}

PageId BTLeafNode::getRoot() {
    PageId p;
    memcpy(&p, buffer + OFFSET_ROOTPID, sizeof(PageId));
    return p;
}

void BTLeafNode::setRoot(PageId p) {
    memcpy(buffer + OFFSET_ROOTPID, &p, sizeof(PageId));
}

// NON LEAF ACCESSOR FUNCTIONS
int BTNonLeafNode::getHeight() {
    int h = 0;
    memcpy(&h, buffer + OFFSET_TREEHEIGHT, sizeof(int));
    return h;
}

void BTNonLeafNode::setHeight(int h) {
    memcpy(buffer + OFFSET_TREEHEIGHT, &h, sizeof(int));
}

PageId BTNonLeafNode::getRoot() {
    PageId p;
    memcpy(&p, buffer + OFFSET_ROOTPID, sizeof(PageId));
    return p;
}

void BTNonLeafNode::setRoot(PageId p) {
    memcpy(buffer + OFFSET_ROOTPID, &p, sizeof(PageId));
}


/*
    Leaf node constructor
 */

BTLeafNode::BTLeafNode(){
    setKey(buffer, 0);
    setHeight(0);
    setRoot(0);
    
    int i = -1;
    memcpy(buffer + OFFSET_NEXTPTR, &i, sizeof(PageId));

}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid,buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	// write the memory buffer to the disk page
    return pf.write(pid,buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
    int keys;
    memcpy(&keys,buffer+OFFSET_KEY,sizeof(int));
	return keys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 	
    /*
     * If there is enough space in the buffer, locate the first
     * eid with a key larger than your key. If a key is found,
     * you must make room for your new entry by shifting the
     * entries to the right. If the new entry is to be inserted
     * at the end of the node, then skip the memmove step. Once
     * space has been created for your entry, insert it into buffer.
     * Increment key count.
     */
    
    //fprintf(stderr, "BTLeafNode::insert Key #: %i\n", getKeyCount());
    // If there is space for it, insert entry
    if ( TAKEN_SPACE + ENTRY_SIZE <= TOTAL_SPACE ) {
        int eid = 0;        // entry id
        
        // Shifts the larger entries to the right one ENTRY_SIZE
        // note: memmove uses intermediate buffer, memcpy does not
        // First entry/pair has eid = 1
        // set eid to first entry >= key, returns 0 if found
		// if locate!=0 that means we place entry at end of our buffer (dont need to move entries to the right)
        if (locate(key,eid) == 0) {
        memmove(buffer+eid*ENTRY_SIZE,
               buffer+(eid-1)*ENTRY_SIZE,
               TAKEN_SPACE-(eid-1)*ENTRY_SIZE);
        }
        
        // Insert my entry
        int offset = (eid-1)*ENTRY_SIZE;
        memcpy(buffer + offset, &rid.pid, sizeof(rid.pid));
        memcpy(buffer + offset+sizeof(rid.pid), &rid.sid, sizeof(rid.sid));
        memcpy(buffer + offset+sizeof(RecordId), &key, sizeof(key));
        
        //keys++;
        incrementKey(buffer);
    }
    else {
        //printf("hello leaf\n");
        return RC_NODE_FULL;
    }
    
	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */

// NOTE: ADDED PARAMETER PageId siblingPid !!!!
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	// split first and get the siblingKey
    // compare siblingKey to key to be inserted
    // insert the key into either the current Leaf Node or the
    // sibling leaf node
   // printf("--- LEAF INSERT AND SPLIT BEGIN\n");
    int new_eid;
    RC rc = locate(key,new_eid);

//    fprintf(stderr, "Before: total entries = %i\n", TOTAL_ENTRIES);

    int split_eid = TOTAL_ENTRIES/2+1;
    
    int flag = 0;               // 0 = insert on left, 1 = insert on right
    if(new_eid > split_eid) { // want to insert into sibling on the right
        //split_eid++;          // so leave one more entry on the left to balance
        flag = 1;
    }
    
//    fprintf(stderr, "Before: split_eid = %i\n", split_eid);
//    fprintf(stderr, "Before: new_eid = %i\n", new_eid);

    
    // Copy right side of the split to sibling node
    int size_left = (split_eid-1)*ENTRY_SIZE;
    int size_right = TAKEN_SPACE - size_left;
    memcpy(sibling.buffer,
           buffer+size_left,
           size_right);
    
    // Update sibling nodes metadata
    setKey(sibling.buffer, size_right/(ENTRY_SIZE));
    setKey(buffer, size_left/(ENTRY_SIZE));
    
    // set new node's next pointer
 	int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    PageId nextPtr = getNextNodePtr();
    memcpy(sibling.buffer+next_pid_offset, &nextPtr, sizeof(PageId));    

    // Clean the contents of the original node
    memset(buffer+size_left,'\0',size_right);
    
    // Insert the new entry
    RC r;
    if (flag==1)  { // insert into right side
//        printf("-- INSERT INTO RIGHT SIDE\n");
        r = sibling.insert(key,rid);
        setKey( sibling.buffer, (size_right+ENTRY_SIZE)/ENTRY_SIZE );
    }
    else {  // insert into left side
//        printf("-- INSERT INTO LEFT SIDE\n");
        r = insert(key,rid);
        //keys = (size_left+ENTRY_SIZE)/ENTRY_SIZE;
        setKey( buffer, (size_left+ENTRY_SIZE)/ENTRY_SIZE );
    }
//    printf("-- INSERT COMPLETE\n");

 //   fprintf(stderr, "AFTER: original total entries = %i\n", getKeyCount());
//    fprintf(stderr, "AFTER: sibling total entries = %i\n", sibling.getKeyCount());
    
    // Set siblingKey to the first key of the sibling
    memcpy(&siblingKey,sibling.buffer+sizeof(RecordId), sizeof(int));
    
//    fprintf(stderr, "SiblingKey = %i\n", siblingKey);

  //  printf("--- INSERT AND SPLIT END\n");

	return r; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
    /*
     * Loop through all of the current entries. Each iteration,
     * get the corresponding key and compare it to the search key.
     * If key>=searchKey then you've found your eid. If never found,
     * then that means there is no match. Set eid to end of the entries
     * and return RC_NO_SUCH_RECORD indicating no match.
     */
    
    // helper variables
   // int start_offset = sizeof(RecordId);    // Offset to first key
   // int nextKey_offset = sizeof(RecordId)+sizeof(int);  // Offset to next key value
//    printf("---- LOCATE THE ENTRY ----- \n");

    int key = 0;
    RecordId rid;
    int cur_eid;
//    printf("Loop through %i entries\n", TOTAL_ENTRIES);
    for (cur_eid=1; cur_eid <= TOTAL_ENTRIES; cur_eid++) {
        if (readEntry(cur_eid,key,rid) == 0) {// readEntry returns 0 on success
//            fprintf(stderr,">>> key: %i, searchKey = %i \n", key,searchKey);
            if (key >= searchKey) {
//                fprintf(stderr,"found larger key at eid: %i\n", cur_eid);
                eid = cur_eid;
                return 0;
            }
        }
    }
    // SearchKey is larger than all current keys
    // return eid to the eid after last spot (TOTAL_ENTRIES+1)
//    printf("Just returning last spot\n");
    eid = cur_eid;
    return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
    /*
     * - Find the offsets to the eid structure and the key
     * - Put the sid,pid, and key char arrays into a buffer
     *   for conversion to int
     * - convert buffers to integers
     */
    if (eid>getKeyCount()) return RC_NO_SUCH_RECORD;
    
    // Get offsets to different values
    int offsetToRID_PID = (eid-1)*ENTRY_SIZE;
    int offsetToRID_SID = offsetToRID_PID+sizeof(PageId);
    int offsetToKey = offsetToRID_SID+sizeof(int);
    
    // rid.pid
    memcpy(&rid.pid,buffer+offsetToRID_PID, sizeof(PageId));
    
    // rid.sid
    memcpy(&rid.sid,buffer+offsetToRID_SID, sizeof(int));
    
    // key
    memcpy(&key,buffer+offsetToKey, sizeof(int));
    
    return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{   
    PageId pid;
    memcpy(&pid,buffer + OFFSET_NEXTPTR, sizeof(PageId));
    
    return pid; 
}


/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ //
    //int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    //memcpy(buffer+next_pid_offset,&pid,sizeof(PageId));
    memcpy(buffer+OFFSET_NEXTPTR,&pid,sizeof(PageId));
    int n;
    memcpy(&n ,buffer+OFFSET_NEXTPTR,sizeof(PageId)); 
   // printf("Next node pointer set to: %i \n" , n);

    return 0;
}

/*
 *  BTNonLeadNode constructor. Sets the key in buffer to 0.
 */
BTNonLeafNode::BTNonLeafNode(){
    setKey(buffer, 0);
    setHeight(0);
    setRoot(0);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf){ 
	return pf.read(pid,buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf){ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount(){ 
    int keys;
    memcpy(&keys,buffer+OFFSET_KEY,sizeof(int));
	return keys;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid){ 
	/*
     * If there is enough space in the buffer, locate the first
     * eid with a key larger than your key. If a key is found,
     * you must make room for your new entry by shifting the
     * entries to the right. If the new entry is to be inserted
     * at the end of the node, then skip the memmove step. Once
     * space has been created for your entry, insert it into buffer.
     * Increment key count.
     */
    
    // If there is space for it, insert entry
    if ( NL_TAKEN_SPACE + NL_ENTRY_SIZE <= NL_TOTAL_SPACE ) {        
        // Shifts the larger entries to the right one ENTRY_SIZE
        // note: memmove uses intermediate buffer, memcpy does not
        // First entry/pair has eid = 1
        // set eid to first entry >= key, returns 0 if found
		// if locate!=0 that means we place entry at end of our buffer (dont need to move entries to the right)
        int eid = 0;        // entry id locate: @[IN] eid
        if (locate(key,eid) == 0) {
               memmove(buffer+eid*NL_ENTRY_SIZE+NL_OFFSET_PID,
                       buffer+(eid-1)*NL_ENTRY_SIZE+NL_OFFSET_PID,
                       NL_TAKEN_SPACE-((eid-1)*NL_ENTRY_SIZE+NL_OFFSET_PID));
        }
        
        // Insert the entry into buffer
        // note: each key is associated with the pid on its RIGHT
        // furthermost pid is unassociated with a key and never moves
        
        memcpy(buffer+(eid-1)*NL_ENTRY_SIZE+NL_OFFSET_PID, 
               &key, 
               sizeof(key));
        
        memcpy(buffer+(eid-1)*NL_ENTRY_SIZE+NL_OFFSET_PID+sizeof(int), 
               &pid,
               sizeof(pid));

        //keys++;
        incrementKey(buffer);
    }
    else {
        return RC_NODE_FULL;
    }
    
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	// split first and get the siblingKey
    // compare siblingKey to key to be inserted
    // insert the key into either the current Leaf Node or the
    // sibling leaf node
    
 //   printf("----- START: Nonleaf insert and split ----\n");
    
    int new_eid;
    RC rc = locate(key,new_eid);

    int split_eid = NL_TOTAL_ENTRIES/2+1;
    
    int flag = 0;               // 0 = insert on left, 1 = insert on right
    if(new_eid > split_eid) { // want to insert into sibling on the right
        //split_eid++;          // so leave one more entry on the left to balance
        flag = 1;
    }
    //
    // Copy right side of the split to new node
    int size_left = (split_eid-1)*NL_ENTRY_SIZE + NL_OFFSET_PID;
    int size_right = NL_TAKEN_SPACE - size_left;
    
    // note: offset by pid to leave room for first pid
    memcpy(sibling.buffer+NL_OFFSET_PID,
           buffer+size_left,
           size_right);
    
    // Update key size meta data
    setKey(buffer, (size_left-NL_OFFSET_PID)/NL_ENTRY_SIZE);
    setKey(sibling.buffer, size_right/NL_ENTRY_SIZE);

    // set new node's next pointer and this node's next pointer
	// TODO: Check later, up to us whether we do this here or in index
    /*int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    memset(sibling.buffer+next_pid_offset,getNextNodePtr(),sizeof(PageId));
    memset(buffer+next_pid_offset, siblingPid, sizeof(PageId));
    */

    // Clean the contents of the original node
    memset(buffer+size_left,'\0',size_right);
    
    // Insert the new entry and set # of keys
    RC r;
    if (flag==1)  { // insert into right side
        r = sibling.insert(key,pid);
        //sibling.keys = (size_right+NL_ENTRY_SIZE)/NL_ENTRY_SIZE;
        setKey(sibling.buffer, (size_right+NL_ENTRY_SIZE)/NL_ENTRY_SIZE);
    }
    else {  // insert into left side
        r = insert(key,pid);
        //keys = (size_left+NL_ENTRY_SIZE)/NL_ENTRY_SIZE;
        setKey(buffer, (size_left+NL_ENTRY_SIZE-NL_OFFSET_PID)/NL_ENTRY_SIZE);
    }
    
    // Get the first key of the sibling - same as the middle node to be pushed up
    memcpy(&midKey,sibling.buffer+NL_OFFSET_PID, sizeof(int));

	// erase the midKey because it will be pushed up
    // shifts everything to the left, taking the midKeys pid from it
	memmove(sibling.buffer,sibling.buffer+NL_OFFSET_PID+sizeof(int),NL_TAKEN_SPACE-NL_OFFSET_PID-sizeof(int));

    decrementKey(sibling.buffer);
	memset(sibling.buffer+NL_TAKEN_SPACE,'\0',NL_ENTRY_SIZE);
	
	return r;
}

// HELPER FUNCTION
RC BTNonLeafNode::readEntry(int eid, int& key, PageId& pid)
{ 
    /*
     * - Find the offsets to the pid and key
     * - Put the pid and key char arrays into a buffer
     *   for conversion to int
     * - convert buffers to integers
     */
    if (eid>getKeyCount()) return RC_NO_SUCH_RECORD;

    // Get offsets to different values
    int offsetToKey = (eid-1)*NL_ENTRY_SIZE+NL_OFFSET_PID;
    int offsetToPID = offsetToKey+sizeof(int);

    // pid
    memcpy(&pid,buffer+offsetToPID, sizeof(PageId));

    // key
    memcpy(&key,buffer+offsetToKey, sizeof(int));

    return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
// HELPER FUNCTION
RC BTNonLeafNode::locate(int searchKey, int& eid)
{ 
    /*
     * Loop through all of the current entries. Each iteration,
     * get the corresponding key and compare it to the search key.
     * If key>=searchKey then you've found your eid. If never found,
     * then that means there is no match. Set eid to end of the entries
     * and return RC_NO_SUCH_RECORD indicating no match.
     */

 //   printf("-- NonLeaf locate : total entries = %i \n", NL_TOTAL_ENTRIES);
    int key = 0;
    int cur_eid = 0;
    int cur_pid = 0;
    for (cur_eid=1; cur_eid <= NL_TOTAL_ENTRIES; cur_eid++) {
        if (readEntry(cur_eid,key,cur_pid) == 0) {// readEntry returns 0 on success
//            printf("Comparing key: %i to searchKey: %i\n", key, searchKey);

            if (key >= searchKey) {
 //               printf("Found larger key = %i \n", key);

                eid = cur_eid;
                return 0;
            }
        }
    }
    // SearchKey is larger than all current keys
    // return eid to the eid after last spot (TOTAL_ENTRIES+1)
//    printf("Just found last eid = %i \n", cur_eid);

    eid = cur_eid;
    
 //   printf("-- END NonLeaf locate : total entries = %i \n", NL_TOTAL_ENTRIES);
	return RC_NO_SUCH_RECORD;
}

 /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
    // find the first key that is bigger than my search key
    // then return the pointer right before it
    // if it is the biggest key, it'll return the last eid
    // and still be the correct pointer
    
    int eid = 0;
    int key = 0;
    if (locate(searchKey, eid) == 0) {
        // get the pointer to the left of the first key that was found
        // to be larger than your key
        //    readEntry(eid, key, pid);
        memcpy(&pid, buffer+(eid-1)*NL_ENTRY_SIZE, sizeof(PageId));
//        printf("LocateChildPtr found pid : %i \n", pid);
    }
    else {
        // find the last eid and get its right pointer
        memcpy(&pid,buffer+NL_TAKEN_SPACE-sizeof(PageId), sizeof(PageId));
//        printf("LocateChildPtr found last pid : %i \n", pid);
    }
    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
   // printf("--- INITIALIZING ROOT with pid, key, pid : %i ---\n", pid1, key, pid2);
    // set the key and two surrounding pids in the root
    // note: meta data of root will be set in BTreeIndex
    memcpy(buffer,&pid1,sizeof(PageId));
    memcpy(buffer+sizeof(PageId),&key,sizeof(int));
    memcpy(buffer+NL_ENTRY_SIZE,&pid2,sizeof(PageId));
    
    // increment key
    // note: constructor set key = 0 originally
    incrementKey(buffer);
    return 0;
}

